BOJ23044 트리 조각하기

풀이

편의상 C[i]=0인 점을 검은점, C[i]=1인 점을 하얀점이라고 합시다. 문제는 몇 개의 하얀점과 세기 p를 선택해서 검은점은 그대로이면서 모든 하얀점을 제거할때 가능한 최대 세기 p를 구하는 문제입니다.

아래와 같은 관찰을 할 수 있습니다.

P=1인 경우: 모든 검은점들로부터 거리가 1이상인 하얀점들에 폭탄을 설치할 수 있습니다. (특히, 이 경우는 항상 모든 하얀점을 제거할 수 있음)

P=i인 경우: 모든 검은점들로부터 거리가 i이상인 하얀점들에 폭탄을 설치할 수 있습니다.

임의의 P에 대해 모든 검은점들로부터 거리가 P이상인 하얀점들에 폭탄을 설치할 수 있습니다.

그리고 다음과 같은 단조성도 존재합니다.

P에서 설치가능한 하얀점들 집합 ⊇ P+1에서 설치가능한 하얀점들 집합

P에서 폭발로 제거가능한 하얀점들 ⊇ P+1에서 폭발로 제거가능한 하얀점들

정리하자면 P=1인경우 항상 모든 하얀점을 제거할 수 있고, 단조성2를 사용해서 모든 하얀점을 제거할 수 있는 최대세기 P를 구해줄 수 있습니다.

폭발로 제거가능한 하얀점들은 아래의 두 번의 bfs로 구해줄 수 있습니다. 검은점들과 인접한 하얀점들을 시작점으로 하는 multisource bfs를 하면, 모든 하얀점에 대해 제일 가까운 검은점까지의 거리를 알 수 있습니다. 위에서 구한 거리가 P이상인 점들을 시작점으로 하는 multisource bfs를 하면, 모든 하얀점들의 거리가 P미만인 경우 모든 하얀점을 제거할 수 있다는 의미입니다. 코드: http://boj.kr/3162bb486e12472ea8bd20acfcf928f3